import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    /**
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     */
    public static List<Brackets> sList;

    public List<String> generateParenthesis(int n) {
        int[] mem = new int[n];

        sList = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            sList.add(new Brackets());
        }

        Set<String> result = new HashSet<>();
        iteration(0, n, mem, result);
        return new ArrayList<>(result);
    }

    private static void iteration(int start, int n, int[] mem, Set<String> result) {
        if (start < n) {
            for (int i = 0; i <= start; i++) {
                mem[start] = i;
                iteration(start + 1, n, mem, result);
            }
        } else {
            result.add(toBrackets(mem));
        }
    }

    private static String toBrackets(int[] mem) {
        for (Brackets b : sList) {
            b.inIdx = 0;
            b.sonList.clear();
        }
        for (int i = 0; i < mem.length; i++) {
            int val = mem[i];
            if (val == 0) {
                continue;
            }
            sList.get(i).inIdx = val;
            sList.get(val - 1).sonList.add(sList.get(i));
        }

        StringBuilder sb = new StringBuilder();
        for (Brackets b : sList) {
            if (b.inIdx == 0) {
                b.toString(sb);
            }
        }
        return sb.toString();
    }

    private static class Brackets {
        private Integer inIdx = 0;
        private final List<Brackets> sonList = new ArrayList<>();

        public void toString(StringBuilder sb) {
            sb.append("(");
            if (sonList.size() > 0) {
                for (Brackets b : sonList) {
                    b.toString(sb);
                }
            }
            sb.append(")");
        }
    }

}
